/* Copyright (c) CERN (except method fwt)
 * * Artistic License 2.0
 * */

import java.util.Random;
import java.lang.Math;
import java.util.Arrays;

/**
 * Plain histogram based pseudo distribution
 *
 * @author Xavier Grehant
 */
public class Histo extends DistroUtils implements Distro {

/**
 * Parameters of the distribution: number of occurences in bins
 */
   int[] params;

/**
 * Histogram precision
 */
   double step;
   
/**
 * Histogram maximum value
 */
   int max;
   
/**
 * A uniform random number generator.
 */
   Random rand;

/**
 * Constructor taking a sample set and the number of params.
 * Samples are sorted. It's just a list but imagine that x values go from 0 to 1
 * by steps of 1/N where N is the number of samples.
 * We obtain an approximation of P(X > x).
 * @param array the sample set.
 * @param paramn number of parameters of the pseudo-distribution.
 */
   public Histo(int[] array, int paramn) {
      rand = new Random();
      Arrays.sort(array);
      this.max = array[array.length - 1];
      this.step = (double) max / (double) paramn;
      this.params = dispatch(array, paramn);
   }

/**
 * Integer Array flip
 * @return flipped array.
 * @param array array to flip.
 */
   int[] flip(int[] array) {
      int[] output = new int[array.length];
      for (int k = 0; k < array.length; k++)
         output[array.length - 1 - k] = array[k];
      return output;
   }

/**
 * Dispatching data in the histogram
 * @return the first parameters of the DCT.
 * @param array the samples.
 * @param paramn the number of parameters in the output.
 * @return a histogram of increasing values.
 */
   int[] dispatch(int[] array, int paramn) {
      int[] output = new int[paramn];
      Arrays.fill(output, 0);
      int k = 0;
      for (int n = 0; n < array.length; n++) { // array is sorted
         if ((double) array[n] <=  ((double) k + 1.) * step)
            output[k] = output[k] + 1;
         else k++;
         }
      return output;
   }

/**
 * inverse cdf
 * @return the value of the modeled function at the specified point,
 *    supposing the function is defined between 0 and 1.
 * @param value at the specified point.
 */
   double icdf(double value) {
      double total = (double) count();
      long cumul = 0;
      int index = 0;
      for (index = 0; index < params.length; index++) {
         cumul += (long) params[index];
         if ((double) cumul / total >= value) break;
         }
      return (double) index * step;
   }

/**
 * size of the histogram
 * @return the number of occurences in the histogram.
 */
   long count() {
      long count = 0;
      for (int i = 0; i < params.length; i++) {
         count += (long) params[i];
         }
      return count;
   }     

/**
 * Random number generator according to the pseudo-distribution.
 * @return random number according to the pseudo-distribution.
 */
   public double nextDouble() {
      return icdf(rand.nextDouble());
   }

/**
 * Cumulative density function of the pseudo-distribution.
 * @return P(X <= x)
 * @param value the point at which the cdf is calculated.
 */
   public double cdf(double value) {
      int index = 0;
      long cumul = 0;
      for (index = 0; index < params.length; index++) {
         cumul += (long) params[index];
         if (((double) index) * step >= value) break;
         }
      return (double) cumul / (double) count();
   }
}
